package dataS.array;

public class OrderArray {
    private int[] array = null;
    //数组有效长度
    public int length = 0;

    public OrderArray() {
        this.array = new int[50];
    }

    public OrderArray(int size) {
        this.array = new int[size];
    }

    //此处有许多细节
    public void insert(int value) {
        //如果插入的元素   小于从前往后遍历的某个元素（记录该位置），则把该元素之后及之后元素后移，然后赋值，length++
        int i;
        for (i = 0; i < length; i++) {
            if (value < array[i])
                break;
        }
        for (int j = length - 1; j >=i; j--) {
            array[j+1] = array[j];
        }
        array[i] = value;

        length++;

    }

    public void travel() {
        System.out.print("[");
        for (int i = 0; i < length; i++) {
            System.out.print(array[i]);
            if (i < length - 1)
                System.out.print(",");
        }
        System.out.println("]");
    }
    //二分查找，返回索引
    public int binarySearch(int value){
        int left=0,right=length-1;
        int mid;

        while(left<=right){
            mid=(left+right)/2;
            //mid=(right-left)>>>1;
            //mid=left+(right-left)/2;

            if(value==array[mid])
                return mid;
            if(value<array[mid]){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return -1;
    }
    public int binarySearchByRecursion(int value,int begin,int end){
        int mid=(begin+end)/2;

        if(array[mid]==value)
            return mid;
        if(begin>end)
            return -1;
        if(value<array[mid]){
            end=mid-1;
            return binarySearchByRecursion(value,begin,end);
        }else{
            begin=mid+1;
            return binarySearchByRecursion(value,begin,end);
        }
    }


}
